#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "unordered_set"

using namespace std;

vector<int> father;

void init(int n) {
    for (int i = 0; i < n; ++i) {
        father[i] = i;//自己的父节点等于自己
    }
}

int find(int u) {
    if (u == father[u])
        return u;//如果自己等于自己的父亲直接返回
    else {
        father[u] = find(father[u]);//当前自己父节点= 最后的那个跟节点
        return father[u];
    }

}

//把v 加入u中
void join(int u, int v) {
    u = find(u);//寻找u的父节点
    v = find(v);//寻找v的父节点

    if (v == u)
        return;

    father[v] = u;
}

// 判断 u 和 v是否找到同一个根，本题用不上
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

//isConnected = [[1,1,0],[1,1,0],[0,0,1]]
int findCircleNum(vector<vector<int>> &isConnected) {

    int n = isConnected.size();
    father.resize(n);
    init(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (isConnected[i][j] == 1)
                join(i, j);
        }

    }
    //并查集构造成功

    unordered_set<int> uset;

    for (int i = 0; i < n; ++i) {
        uset.insert(find(i));
    }


    return uset.size();

}